package cn.whdream.datastructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 
 * @author admin 图 TODO 深度广度优先遍历方法有问题，可能需要调查资料核对一下
 */

public class GraphDemo {
	private ArrayList<String> vertexList;// 顶点集合
	private int[][] edges;// 存储图对应的邻结矩阵
	private int numOfEdges;// 边的数目
	private boolean[] isVisited;

	public static void main(String[] args) {
		//GraphDemo graph = TestWords();

		// graph.showGraph();
		String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
		int n = Vertexs.length;
		GraphDemo graph = new GraphDemo(n);
		for (String string : Vertexs) {
			graph.insertVertex(string);
		}
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.insertEdge(3, 7, 1);
		graph.insertEdge(4, 7, 1);
		graph.insertEdge(2, 5, 1);
		graph.insertEdge(2, 6, 1);
		graph.insertEdge(5, 6, 1);
		
		graph.bfs();
	}

	private static GraphDemo TestWords() {
		String vertexValue[] = { "A", "B", "C", "D", "E" };

		int n = vertexValue.length;
		GraphDemo graph = new GraphDemo(n);
		for (String string : vertexValue) {
			graph.insertVertex(string);
		}
		// 插入点
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 0, 1);// B-A
		graph.insertEdge(1, 2, 1);// B-C
		graph.insertEdge(1, 3, 1);// B-D
		graph.insertEdge(1, 4, 1);// B-E
		graph.insertEdge(2, 0, 1);
		graph.insertEdge(2, 1, 1);
		graph.insertEdge(3, 1, 1);
		graph.insertEdge(4, 1, 1);
		return graph;
	}

	public GraphDemo(int n) {
		super();
		// 初始化
		edges = new int[n][n];
		vertexList = new ArrayList<>();
		numOfEdges = 0;
		isVisited = new boolean[n];
	}

	/**
	 * 得到第一个链接节点下标
	 * 
	 * @param index
	 * @return
	 */
	public int getFirstNeighbor(int index) {
		for (int i = 0; i < vertexList.size(); i++) {
			// 指定对应的行数，即指定对应是 哪个一个字母 ，然后遍历每一列计算是否可以访问
			if (edges[index][i] > 0) {
				// 可以返回的，返回对应的列数，由于行数是外界传的，所以外界是知道行数的
				return i;
			}
		}
		return -1;
	}

	/**
	 * 根据前一个，获取笑一个邻接的结点下标
	 * 
	 * @param v1
	 * @param v2
	 * @return
	 */
	public int getNextNeighbor(int v1, int v2) {
		// 基于前一个坐标，遍历之后的列还有哪些需要访问的
		for (int i = v2 + 1; i < vertexList.size(); i++) {
			if (edges[v1][i] > 0) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 深度
	 */
	public void dfs(boolean[] isVisited, int i) {
		// 当遍历开始，就打印字母，获取对应index
		System.out.print(getValueByIndex(i) + "->");
		// 告诉对应访问过的结点 已经 访问过了，避免横向的字母访问过一遍，纵向的字母再访问一遍
		isVisited[i] = true;
		// 由于获取的字母的index和 二维数组的行的字母都是一一对应的，所以直接传入即可
		int w = getFirstNeighbor(i);// 获取到可以访问的第一个字母的列的index
		// 不为-1则继续执行，so意味着 如果为 -1，就说明该字母和对应的列的字母没有路径可以通向
		while (w != -1) {
			// 访问没有访问过的界面
			if (!isVisited[w]) {
				// 深度优先遍历时，由于当遇到下一个结点，就换下一个结点开始遍历；所以要通过递归进行标记
				// 又因为递归时， a到c和c到a是重复路径，无方向的图无需重复遍历，所以直接标记为通过就可以了
				dfs(isVisited, w);
			}
			// 如果已经访问过了，就切换下一个
			w = getNextNeighbor(i, w);
		}
	}

	public void dfs() {
		//原来课上说需要循环，但是实际不需要循环
		dfs(isVisited, 0);
	}

	public void bfs(boolean[] isVisited, int i) {
		int u; // 队列头的下标
		int w;
		LinkedList<Integer> queue = new LinkedList<>();
		System.out.print(getValueByIndex(i) + "=>");
		isVisited[i] = true;
		queue.addLast(i);
		while (!queue.isEmpty()) {
			u = (int) queue.removeFirst();
			w = getFirstNeighbor(u);
			while (w != -1) {
				if (!isVisited[w]) {
					System.out.print(getValueByIndex(w) + "=>");
					isVisited[w] = true;
					queue.addLast(w);
				}
				w = getNextNeighbor(u, w);
			}
			
		}
	}

	public void bfs() {
		//原来课上说需要循环，但是实际不需要循环
		bfs(isVisited, 0);
	}

	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}

	/**
	 * 
	 * @param v1     点下标
	 * @param v2     第二点的下标
	 * @param weight 一次性将对角线的反转的点位同时设置掉
	 */
	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfEdges++;
	}

	private int getNumOfVertex() {
		return vertexList.size();
	}

	public int getNumOfEdges() {
		return numOfEdges;
	}

	// 返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
	public String getValueByIndex(int i) {
		return vertexList.get(i);
	}

	// 返回v1和v2的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}

	// 显示图对应的矩阵
	public void showGraph() {
		for (int[] link : edges) {
			System.err.println(Arrays.toString(link));
		}
	}
}
